package com.wss.lsl.test.driven.arithmetic.substr;

/**
 * 最大重复子字符串
 * 
 * @author sean
 *
 */
public class MaxRepeatSubstring {

	private char[] chars; // 字符数组
	private int[] subIndexs; // 下标数据
	private int maxI;
	private int maxL = 0;

	public MaxRepeatSubstring(char[] chars) {
		super();
		this.chars = chars;
		int length = this.chars.length;

		// 初始化后缀数组
		subIndexs = new int[length];
		for (int i = 0; i < length; i++) {
			subIndexs[i] = i;
		}

		// 排序
		qsort(0, length - 1);

		// 得到最大重复子串：相邻的两个子串比较
		int thisLen;
		for (int i = 0; i < length - 1; i++) {
			if ((thisLen = comLen(subIndexs[i], subIndexs[i + 1])) > maxL) {
				maxL = thisLen;
				maxI = i;
			}
		}
	}

	private int comLen(int i, int j) {
		System.out.println(String.format("%s %s", i, j));
		int len = 0;
		for (int t = 0; t < Math.min(chars.length - i, chars.length - j); t++) {
			if (chars[t + i] == chars[t + j]) {
				len++;
			} else {
				break;
			}
		}

		return len;
	}

	private void qsort(int l, int u) {

		if (l >= u) {
			return;
		}

		int tBegin = subIndexs[l];
		int iBegin;
		int m = l;
		boolean result = false;
		for (int i = l + 1; i <= u; i++) {
			iBegin = subIndexs[i];
			result = false;
			for (int j = 0; j < Math.min(chars.length - tBegin, chars.length
					- iBegin); j++) {// 比较子字符数组的大小
				if (chars[iBegin + j] < chars[tBegin + j]) {
					result = true;
					break;
				}
			}

			if (result) {
				m++;
				swap(i, m);
			}
		}

		swap(l, m);
		qsort(l, m - 1);
		qsort(m + 1, u);
	}

	private void swap(int i, int j) {
		int temp = subIndexs[i];
		subIndexs[i] = subIndexs[j];
		subIndexs[j] = temp;
	}

	public void printMaxSubstr() {
		for (int i = 0; i < maxL; i++) {
			System.out.print(chars[i + subIndexs[maxI]]);
		}
	}

	public void report() {
		for (int i = 0; i < subIndexs.length; i++) {
			System.out.print(String.format("index=%s substr=", subIndexs[i]));
			for (int j = subIndexs[i]; j < chars.length; j++) {
				System.out.print(chars[j]);
			}
			System.out.println();
		}
	}
}
